# -*- coding: utf-8 -*-
"""
    Time    : 2021/1/6 10:17 上午
    Author  : Thinkgamer
    File    : 017-电话号码的字母组合.py
    Desc    : https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
"""
"""
给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

2 -> abc
3 -> def
4 -> ghi
5 -> jkl
6 -> mno
7 -> pqrs
8 -> tuv
9 -> wxyz

示例:
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
"""

str_number_dict = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}

# 56ms 10.75% | 14.9mb 11.75%
"""
	思路：固定第一位，剩下的进行递归遍历搜索
"""
def letter_combinations(digits):
	def search(char, queue):
		# queue 为空表明遍历完成，返回最后遍历的字符
		if not queue:
			return char
		# 不为空的话，依次进行遍历
		temp = list()
		_len = 0
		while _len < len(queue):
			num = queue[_len]
			_len += 1
			for c in str_number_dict[num]:
				search_result = search(c, queue[_len:])
				for one in search_result:
					temp.append(char + one)
			break
		return temp
	
	if len(digits) == 0:
		return []
	else:
		result = list()
		first = digits[0]
		for char in str_number_dict[first]:
			result += search(char, digits[1:])
		return result


for one in ["", "2", "23", "234"]:
	result = letter_combinations(one)
	print("one: {}, result: {}".format(one, result))
